1. Field of the Invention
The present invention relates to techniques for routing nets during the process of designing of an integrated circuit. More specifically, the present invention relates to a method and a system for integrating a Boolean Satisfiability (SAT) solver into a router to facilitate solving a complicated routing problem during the design of an integrated circuit (IC).
2. Related Art
Advances in semiconductor technology presently make it possible to integrate large-scale systems, including hundreds of millions of transistors, onto a single semiconductor chip. This dramatic increase in semiconductor integration densities has made it considerably more challenging to efficiently perform routing in such a large-scale IC chip.
Routing an integrated circuit involves determining routes for metal wires which electrically connect integrated circuit devices to produce circuits that perform desired functions. Large scale IC chips are typically routed using automatic routing software, which is typically referred to as a “routing system” or “router.” A router receives a design for an IC chip which includes a “netlist” that specifies connectivity between circuit nodes. The router then determines how to route conductors through the physical layout to connect associated components on the netlist. During this process, the router adheres to a set of design rules while routing wires between circuit nodes.
A routing process generally includes a “global-routing phase,” which is followed by a “detailed-routing phase.” The global-routing phase determines an approximate route for the wires across the chip. In doing so, a global router typically divides the chip into rectangular tiles, and then maps the connection points to the tile centers, and subsequently routes the connections over a tile adjacency graph (also called a “global grid graph”).
During the subsequent detailed-routing phase, a detailed router starts with the coarse results produced by the global router, and implements specific connections between pairs of points within a region of chip, which is referred to as a “switchbox.” These connections specify with complete precision where each wire is located.
For a given pair of points, a “routing engine” is used to find a connection between those points. The resulting connection may use wires that had been routed before the routing engine was used for the given pair of points. The router determines: how each net in the netlist is decomposed into pairs of points, the order that those pairs are routed using the routing engine, and which connections should be ripped-up and rerouted, while searching for a desirable routing for each switchbox.
A maze routing engine (also referred to as a “Lee routing engine”) is one type of routing engine which routes a given pair of points by progressively searching through some or all of the grid locations between the given pair of points. A maze routing engine is typically guaranteed to find a connection between the pair of points if such a connection exists. Furthermore, a maze routing engine is also capable of finding a shortest path if there is more than one possible path.
However, in some cases a router can generate a set of connections for a switchbox which fails to satisfy all of the design rules. In such cases, a user will receive feedback from the router that a design rule violation has occurred. Typically, the user will have to perform a number of actions, such as: (1) entering the routing environment, for example through a graphical user interface (GUI), locating the violating route, and attempting to fix the route by hand; or alternatively (2) returning to earlier steps of the routing flow and relaxing the design constraints by, for example, increasing the size of the area being routed. Unfortunately, such manual intervention is tedious and can slow down the routing process.
Hence, what is needed is a method and a system that can improve the routability of a router, and which can thereby release the user from the task of manually intervening in the routing process.